home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1998 / MacHack 1998.toast / Programming Contest / Secret Solutions Folder / Problem 06 - Legal Chess Moves / Solution.cp < prev    next >
Encoding:
Text File  |  1998-06-12  |  22.8 KB  |  715 lines  |  [TEXT/CWIE]
  1. #if 0
  2. Problem 13 - Legal Chess Moves
  3.  
  4. Deep Thought has beaten mankind as the game once thought to exemplify human intuition.  Our MacHack laboratory is secretly constructing an implant that will neutralize the calculation advantage held by the computer, and restore mankind to its rightful place as the champion of chess, through intuition and cunning.  Your job is to write the code that will calculate the board position resulting from a sequence of moves, along with the legal moves available to the next player.  With this advantage, the human chess master will be able to concentrate on strategy, rather than waste time calculating moves.
  5.  
  6. The prototype for your solution is as follows:
  7.  
  8. typedef enum {kEmpty=0,kWhite,kBlack} PieceColor;
  9. typedef enum {kNone=0,kPawn,kKnight,kBishop,kRook,kQueen,kKing} PieceRank;
  10.  
  11. typedef struct Square {
  12.     UInt16 row;    /* 0..7, white initially occupies rows 0 and 1, black 7 and 6 */
  13.     UInt16 col;    /* 0..7, white king starts at (row,col) == (0,4) */
  14. } Square;
  15.  
  16. typedef struct ChessMove {
  17.     Square fromSquare;
  18.     Square toSquare;
  19.     Boolean capture;
  20.     Square capturedSquare;    /* valid only if capture==TRUE */
  21. } ChessMove;
  22.  
  23. typedef struct ChessPiece {
  24.     PieceColor whichColor;
  25.     PieceRank whichRank;
  26.     Square pieceLocation;
  27. } ChessPiece;
  28.  
  29. pascal void FindLegalChessMoves(
  30.     UInt32 numPriorMoves,
  31.     ChessMove priorMoves[],
  32.     UInt32 *numPiecesRemaining,
  33.     ChessPiece piecesRemaining[],
  34.     UInt32 *numLegalMoves,
  35.     ChessMove legalMoves[]
  36. );
  37.  
  38. Your FindLegalChessMoves routine will be called with a list (priorMoves) of numPriorMoves that have already taken place from the normal initial chessboard. You should model the effects of those moves and generate a list (piecesRemaining) of the numPiecesRemaining pieces remaining, including their location on the board, and a list (legalMoves) of all numLegalMoves legal moves available to the next player.  Remember to include castling moves when appropriate (indicated by moving the king the appropriate two/three squares) and en passant pawn captures.
  39. #endif
  40.  
  41. #include "Solution.h"
  42.  
  43. // Fill in your solution and then submit this folder
  44.  
  45. // Team Name: FILL IN YOUR TEAM NAME!
  46. #include "Solution.h"
  47.  
  48. #include "ProblemUtils.h"
  49. #include "myqsort.h"
  50.  
  51. #include <stdio.h>
  52. #include <Files.h>
  53. #include <Errors.h>
  54.  
  55. #define PRINT_MOVES 0
  56. #define PRINT_PIECES 0
  57. #define PRINT_BOARD 0
  58.  
  59. #define kMaxPiecesRemaining 32
  60. #define kMaxMoves 1024
  61.  
  62. static char gCol[] = "abcdefgh";
  63. static char gRow[] = "12345678";
  64. static char gColor[] = " WB";
  65. static char gRank[] = "-pNBRQK";
  66. #define kKingCol 4
  67. #define kQueenCol 3
  68.  
  69.  
  70. typedef struct Piece {
  71.     PieceColor color;
  72.     PieceRank rank;
  73. } Piece;
  74.  
  75. typedef struct Board {
  76.     Piece sq[8][8];
  77.     Square kingSq;
  78.     ChessMove lastMove;
  79.     Boolean pieceNeverMoved[8][8];
  80. } Board;
  81.  
  82. static void InitBoard(Board *b)
  83. {
  84.     int row,col;
  85.     for (col=0; col<8; col++) {
  86.         b->sq[0][col].color = b->sq[1][col].color = kWhite;
  87.         b->sq[7][col].color = b->sq[6][col].color = kBlack;
  88.         b->sq[2][col].color = b->sq[3][col].color = kEmpty;
  89.         b->sq[4][col].color = b->sq[5][col].color = kEmpty;
  90.         b->sq[1][col].rank = b->sq[6][col].rank = kPawn;
  91.         b->sq[2][col].rank = b->sq[3][col].rank = kNone;
  92.         b->sq[4][col].rank = b->sq[5][col].rank = kNone;
  93.     }
  94.     b->sq[0][0] .rank= b->sq[0][7].rank = b->sq[7][0].rank = b->sq[7][7].rank = kRook;
  95.     b->sq[0][1].rank = b->sq[0][6].rank = b->sq[7][1].rank = b->sq[7][6].rank = kKnight;
  96.     b->sq[0][2].rank = b->sq[0][5].rank = b->sq[7][2].rank = b->sq[7][5].rank = kBishop;
  97.     b->sq[0][kQueenCol].rank = b->sq[7][kQueenCol].rank = kQueen;
  98.     b->sq[0][kKingCol].rank = b->sq[7][kKingCol].rank = kKing;
  99.     for (row=0; row<8; row++) {
  100.         for (col=0; col<8; col++) {
  101.             b->pieceNeverMoved[row][col] = true;
  102.         }
  103.     }
  104.     b->lastMove.fromSquare.row = b->lastMove.fromSquare.col = 0xffff;
  105.     b->lastMove.toSquare.row = b->lastMove.toSquare.col = 0xffff;
  106. }
  107.  
  108. #if PRINT_PIECES
  109. static void PrintPieces(UInt32 numPieces, ChessPiece *piece, char *s)
  110. {
  111.     int j;
  112.     printf("%s %ld\n", s,numPieces);
  113.     for (j=0; j<numPieces; j++) {
  114.         printf("%c%c %c%c\n",
  115.             gColor[piece[j].whichColor],gRank[piece[j].whichRank],
  116.             gCol[piece[j].pieceLocation.col],gRow[piece[j].pieceLocation.row]);
  117.     }
  118. }
  119. #else
  120. static void PrintPieces(UInt32 numPieces, ChessPiece *piece, char *s) {
  121. #pragma unused(numPieces)
  122. #pragma unused(piece)
  123. #pragma unused(s)
  124. };
  125. #endif
  126.  
  127. #if PRINT_MOVES
  128. static void PrintMoves(UInt32 numMoves, ChessMove *move, char *s)
  129. {
  130.     int j;
  131.     printf("%s %ld\n",s,numMoves);
  132.     for (j=0; j<numMoves; j++) {
  133.         printf("%d %c%c%c%c%c",j,
  134.             gCol[move[j].fromSquare.col],gRow[move[j].fromSquare.row],
  135.             move[j].capture ? 'x' : '-',
  136.             gCol[move[j].toSquare.col],gRow[move[j].toSquare.row]);
  137.         if (move[j].capture) {
  138.             printf(" %c%c\n",
  139.                 gCol[move[j].capturedSquare.col],gRow[move[j].capturedSquare.row]);
  140.         } else {
  141.             printf("\n");
  142.         }
  143.     }
  144. }
  145. #else
  146. static void PrintMoves(UInt32 numMoves, ChessMove *move, char *s) {
  147. #pragma unused(numMoves)
  148. #pragma unused(move)
  149. #pragma unused(s)
  150. };
  151. #endif
  152.  
  153. #if PRINT_BOARD
  154. static void PrintBoard(Board *b)
  155. {
  156.     int row,col;
  157.     printf("    a  b  c  d  e  f  g  h \n");
  158.     for (row=7; row>=0; row--) {
  159.         printf("%2d ",row+1);
  160.         for (col=0; col<8; col++) {
  161.             printf("%c%c ",gColor[b->sq[row][col].color], gRank[b->sq[row][col].rank]);            
  162.         }
  163.         printf("\n");
  164.     }
  165.     printf("    %c%c%c%c%c\n\n",
  166.         gCol[b->lastMove.fromSquare.col],gRow[b->lastMove.fromSquare.row],
  167.         b->lastMove.capture ? 'x' : '-',
  168.         gCol[b->lastMove.toSquare.col],gRow[b->lastMove.toSquare.row]    );
  169. }
  170. #else
  171. static void PrintBoard(Board *b) {
  172. #pragma unused(b)
  173. };
  174. #endif
  175.  
  176. static PieceColor OtherColor(PieceColor c)
  177. {
  178.     return (PieceColor)(3 - (int)c);    /* white is 1, black is 2 */
  179. }
  180.  
  181. static Boolean FindKing(Board *b,PieceColor color, Square *kingSq)
  182. {
  183.     int row,col;
  184.     for (row=0; row<8; row++)
  185.         for (col=0; col<8; col++) {
  186.             if ( (b->sq[row][col].color == color) && (b->sq[row][col].rank==kKing)) {
  187.                 kingSq->row = row;    kingSq->col = col;    return true;
  188.             }
  189.         }
  190.     return false;
  191. }
  192.  
  193. static void MovePiece(Board *b, ChessMove *m, PieceColor colorToMove)
  194. {
  195.     int fromRow = m->fromSquare.row;
  196.     int fromCol = m->fromSquare.col;
  197.     int toRow = m->toSquare.row;
  198.     int toCol = m->toSquare.col;
  199.     PieceColor ourColor = b->sq[fromRow][fromCol].color;
  200.     int homeRow = (ourColor==kWhite) ? 0 : 7;
  201.     if (colorToMove != ourColor) printf("** ERR moving wrong color piece\n");
  202.     if (!m->capture) {
  203.         if (b->sq[toRow][toCol].color != kEmpty) {
  204.             printf(" ** bad move fromSq=(%d %d) toSq=(%d %d) our color=%d other color=%d\n",
  205.                 fromRow,fromCol,toRow,toCol,
  206.                 b->sq[fromRow][fromCol].color,b->sq[toRow][toCol].color);
  207.         }
  208.     } else {  // debug test fails incorrectly for en passant
  209. //        if (b->sq[toRow][toCol].color != OtherColor(b->sq[fromRow][fromCol].color)) {
  210. //            printf(" ** bad capture fromSq=(%d %d) toSq=(%d %d) our color=%d other color=%d\n",
  211. //                fromRow,fromCol,toRow,toCol,
  212. //                b->sq[fromRow][fromCol].color,b->sq[toRow][toCol].color);
  213. //        }
  214.         /* includes en passant */
  215.         b->sq[m->capturedSquare.row][m->capturedSquare.col].color = kEmpty;
  216.         b->sq[m->capturedSquare.row][m->capturedSquare.col].rank = kNone;
  217.     }
  218.     /* check castle */
  219.     if ( (b->sq[fromRow][fromCol].rank == kKing) && (fromRow==homeRow) && (fromCol==kKingCol) && 
  220.           (b->sq[fromRow][fromCol].color==ourColor) ) {
  221.             if ( (toCol==2) && (b->sq[fromRow][1].rank==kRook)) {
  222.                 b->sq[fromRow][3].color = b->sq[fromRow][0].color;
  223.                 b->sq[fromRow][3].rank = b->sq[fromRow][0].rank;
  224.                 b->sq[fromRow][0].color = kEmpty;
  225.                 b->sq[fromRow][0].rank = kNone;
  226.             } else if ( (toCol==6)  && (b->sq[fromRow][7].rank==kRook) ) {
  227.                 b->sq[fromRow][5].color = b->sq[fromRow][7].color;
  228.                 b->sq[fromRow][5].rank = b->sq[fromRow][7].rank;
  229.                 b->sq[fromRow][7].color = kEmpty;
  230.                 b->sq[fromRow][7].rank = kNone;
  231.             }
  232.     }
  233.     /* check pawn promotion */
  234.     if ( (b->sq[fromRow][fromCol].rank == kPawn) && (b->sq[fromRow][fromCol].color==ourColor) &&
  235.           (toRow==7-homeRow) ) {
  236.           /* promote in place, move code will update proper location */
  237.         b->sq[toRow][toCol].rank = kQueen;
  238.     } 
  239.     /* update board */
  240.     b->sq[toRow][toCol].color = b->sq[fromRow][fromCol].color;
  241.     b->sq[toRow][toCol].rank = b->sq[fromRow][fromCol].rank;
  242.     b->sq[fromRow][fromCol].color = kEmpty;
  243.     b->sq[fromRow][fromCol].rank = kNone;
  244.     b->pieceNeverMoved[fromRow][fromCol] = false;
  245.     b->pieceNeverMoved[toRow][toCol] = false;
  246.     b->lastMove = *m;
  247.     FindKing(b,ourColor,&b->kingSq);
  248. }
  249.  
  250. static SInt16 gDeltaRow[8] = { 0, 1, 1, 1, 0, -1, -1, -1};
  251. static SInt16 gDeltaCol[8] =  {-1, -1, 0, 1, 1, 1, 0, -1};
  252. static SInt16 gKnightDeltaRow[8] = {1,2,2,1,-1,-2,-2,-1};
  253. static SInt16 gKnightDeltaCol[8] = {-2,-1,1,2,2,1,-1,-2};
  254.  
  255. static Boolean LegalSquare(SInt16 row, SInt16 col) {    /* note need for signed value */
  256.     return ((row>=0) && (row<8) && (col>=0) && (col<8));
  257. }
  258.  
  259. static Boolean LegalRelSquare(Board *b, SInt16 row, SInt16 col, int dir, int dist, Piece *sq)
  260. {
  261.     Boolean result;
  262.     row += gDeltaRow[dir]*dist;
  263.     col += gDeltaCol[dir]*dist;
  264.     result = LegalSquare(row, col);
  265.     if (result) *sq = b->sq[row][col];
  266.     return result;
  267. }
  268.  
  269. static Boolean LegalKnightRelSquare(Board *b, SInt16 row, SInt16 col, int dir, Piece *sq)
  270. {
  271.     Boolean result;
  272.     row += gKnightDeltaRow[dir];
  273.     col += gKnightDeltaCol[dir];
  274.     result = LegalSquare(row,col);
  275.     if (result) *sq = b->sq[row][col];
  276.     return result;
  277. }
  278.  
  279. static Boolean MovesDiagonally(PieceRank rank, UInt16 dist) {
  280.     return ((rank==kQueen)||(rank==kBishop)||( (dist==1) && (rank==kKing) ) );
  281. }
  282.  
  283. static Boolean MovesRectangularly(PieceRank rank, UInt16 dist) {
  284.     return ((rank==kQueen)||(rank==kRook)||( (dist==1) && (rank==kKing) ) );
  285. }
  286.  
  287. static Boolean SquareIsAttacked(Board *b, SInt16 row, SInt16 col)
  288. {
  289.     Piece onSquare;
  290.     PieceColor ourColor = b->sq[row][col].color;
  291.     PieceColor opponentColor = OtherColor(ourColor);
  292.     int dir,dist;
  293.     
  294.     for (dir=1; dir<8; dir+=2) {    /* check diagonals */
  295.         for (dist=1; dist<8; dist++) {    /* check distance */
  296.             if (!LegalRelSquare(b, row, col, dir, dist, &onSquare)) break;
  297.             if (onSquare.color == kEmpty) break;
  298.             if (onSquare.color == ourColor) break;
  299.             if (onSquare.color == opponentColor) {
  300.                 if ( MovesDiagonally(onSquare.rank,dist) )
  301.                     return true;
  302.             } else break;
  303.         }
  304.     }
  305.     
  306.     for (dir=0; dir<8; dir+=2) {    /* check files */
  307.         for (dist=1; dist<8; dist++) {    /* check distance */
  308.             if (!LegalRelSquare(b, row, col, dir, dist, &onSquare)) break;
  309.             if (onSquare.color == kEmpty) break;
  310.             if (onSquare.color == ourColor) break;
  311.             if (onSquare.color == opponentColor) {
  312.                 if ( MovesRectangularly(onSquare.rank,dist) )
  313.                     return true;
  314.             } else {
  315.                 break;
  316.             }
  317.         }
  318.     }
  319.     
  320.     for (dir=0; dir<8; dir++) {    /* check knights */
  321.         if (!LegalKnightRelSquare(b, row, col, dir, &onSquare)) continue;
  322.         if (onSquare.color == kEmpty) continue;
  323.         if (onSquare.color == ourColor) continue;
  324.         if (    (onSquare.color == opponentColor) && (onSquare.rank == kKnight) ) 
  325.             return true;
  326.     }
  327.  
  328.     /* check pawns */
  329.     if (LegalRelSquare(b, row, col, (ourColor==kWhite) ? 1 : 8-1, 1, &onSquare))
  330.         if ( (onSquare.color==opponentColor) && (onSquare.rank==kPawn)) 
  331.             return true;
  332.     if (LegalRelSquare(b, row, col, (ourColor==kWhite) ? 3 : 8-3, 1, &onSquare))
  333.         if ( (onSquare.color==opponentColor) && (onSquare.rank==kPawn)) 
  334.             return true;
  335.     return false;
  336. }
  337.  
  338. static void CreateMove(ChessMove *m, UInt16 row, UInt16 col, int dir, int dist, Piece *sq)
  339. {
  340.     m->fromSquare.row = row;
  341.     m->fromSquare.col = col;
  342.     m->toSquare.row = row + gDeltaRow[dir]*dist;
  343.     m->toSquare.col = col + gDeltaCol[dir]*dist;
  344.     m->capture = false;
  345.     if (sq->color != kEmpty) {    /* pawns need to be handled separately */
  346.         m->capture = true;
  347.         m->capturedSquare = m->toSquare;
  348.     }
  349. }
  350.  
  351. static void CreateKnightMove(ChessMove *m, UInt16 row, UInt16 col, int dir, Piece *sq)
  352. {
  353.     m->fromSquare.row = row;
  354.     m->fromSquare.col = col;
  355.     m->toSquare.row = row + gKnightDeltaRow[dir];
  356.     m->toSquare.col = col + gKnightDeltaCol[dir];
  357.     m->capture = false;
  358.     if (sq->color != kEmpty) {    /* pawns need to be handled separately */
  359.         m->capture = true;
  360.         m->capturedSquare = m->toSquare;
  361.     }
  362. }
  363.  
  364. static Boolean CheckMove(Board *origBoard, ChessMove **moves, SInt16 row, SInt16 col, int dir, int dist, Piece *onSquare,UInt32 *numMovesAdded)
  365. {
  366.     ChessMove theMove;
  367.     Board b = *origBoard;
  368.     if (b.sq[row][col].rank == kKnight) {
  369.         CreateKnightMove(&theMove,row,col,dir,onSquare);
  370.     } else {
  371.         CreateMove(&theMove,row,col,dir,dist,onSquare);
  372.     }
  373.     MovePiece(&b, &theMove, b.sq[row][col].color);
  374.     if (SquareIsAttacked(&b, b.kingSq.row,b.kingSq.col)) {/* moves king into check or leaves king in check */
  375.         return false;
  376.     }
  377.     **moves = theMove;
  378.     (*moves)++;
  379.     ++*numMovesAdded;
  380.     return true;
  381. }
  382.  
  383. static Boolean CheckEPMove(Board *origBoard, ChessMove **moves, SInt16 row, SInt16 col, 
  384.         SInt16 captureRow, SInt16 captureCol,int dir, Piece *onSquare,UInt32 *numMovesAdded)
  385. {
  386.     ChessMove theMove;
  387.     Board b = *origBoard;
  388.     CreateMove(&theMove,row,col,dir,1,onSquare);
  389.     theMove.capturedSquare.row = captureRow;
  390.     theMove.capturedSquare.col = captureCol;
  391.     theMove.capture = true;
  392.     MovePiece(&b, &theMove,b.sq[row][col].color);
  393.     if (SquareIsAttacked(&b, b.kingSq.row,b.kingSq.col)) {/* moves king into check or leaves king in check */
  394.         return false;
  395.     }
  396.     **moves = theMove;
  397.     (*moves)++;
  398.     ++*numMovesAdded;
  399.     return true;
  400. }
  401.  
  402. static UInt32 CreateLegalPawnMoves(Board *origBoard, SInt16 row, SInt16 col, ChessMove *origMoves)
  403. {
  404.     PieceColor ourColor = origBoard->sq[row][col].color;
  405.     PieceColor opponentColor = OtherColor(ourColor);
  406.     UInt32 numMovesAdded = 0;
  407.     Piece onSquare;
  408.     int dir,dist,homeRow,advanceRowDir,enPassantRow;
  409.     ChessMove *moves = origMoves;
  410.         
  411.     if (ourColor==kWhite) {
  412.         dir = 2;
  413.         enPassantRow = 4;
  414.         advanceRowDir = 1;
  415.     } else {
  416.         dir = 8-2;
  417.         enPassantRow = 7-4;
  418.         advanceRowDir = -1;
  419.     }
  420.     dir = ourColor==kWhite ? 2 : 8-2;    /* check moves ahead */
  421.     homeRow = (ourColor==kWhite) ? 1 : 7-1;    /* home row is 1 for white and 6 for black */
  422.     
  423.     /* check move one ahead */
  424.     dist = 1;
  425.     if (    (LegalRelSquare(origBoard, row, col, dir, dist, &onSquare)) &&
  426.             (onSquare.color == kEmpty) ) {
  427.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  428.     }
  429.     
  430.     /* check move two ahead */
  431.     dist = 2;
  432.     if (     (origBoard->pieceNeverMoved[row][col]) && 
  433.             (row == homeRow) &&
  434.             (LegalRelSquare(origBoard, row, col, dir, dist, &onSquare)) /* set onSquare */ &&
  435.             (onSquare.color == kEmpty) ){
  436.             CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  437.     }
  438.     
  439.     /* check capture right (including en passant) */
  440.     dir = ourColor==kWhite ? 3 : 8-3;
  441.     dist=1;
  442.     if (    LegalRelSquare(origBoard, row, col, dir, dist, &onSquare)) {
  443.         if  (onSquare.color == opponentColor) {
  444.             CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  445.         } else {
  446.             SInt16 epCol = col+gDeltaCol[dir];
  447.             if ( (onSquare.color == kEmpty) &&
  448.                         (row==enPassantRow) &&
  449.                         (origBoard->sq[row][epCol].rank == kPawn) &&
  450.                         (origBoard->sq[row][epCol].color == opponentColor) &&
  451.                         (origBoard->lastMove.toSquare.row == enPassantRow) &&
  452.                         (origBoard->lastMove.fromSquare.row == enPassantRow+2*advanceRowDir) &&
  453.                         (origBoard->lastMove.fromSquare.col == col + gDeltaCol[dir]) &&
  454.                         (origBoard->lastMove.toSquare.col == col + gDeltaCol[dir]) ) {
  455.                 CheckEPMove(origBoard,&moves,row,col,row,epCol,dir,&onSquare, &numMovesAdded);
  456.                     
  457. //            printf("** checking en passant (r,c)=(%d %d) ep=(%d %d)\n",
  458. //                row,col,origBoard->lastMove.fromSquare.row,origBoard->lastMove.fromSquare.col);
  459.             }
  460.         }
  461.     }
  462.     
  463.     /* check capture left (including en passant) */
  464.     dir = ourColor==kWhite ? 1 : 8-1;
  465.     dist=1;
  466.     if (    LegalRelSquare(origBoard, row, col, dir, dist, &onSquare)) {
  467.         if  (onSquare.color == opponentColor) {
  468.             CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  469.         } else {
  470.             SInt16 epCol = col+gDeltaCol[dir];
  471.             if ( (onSquare.color == kEmpty) &&
  472.                         (row==enPassantRow) &&
  473.                         (origBoard->sq[row][epCol].rank == kPawn) &&
  474.                         (origBoard->sq[row][epCol].color == opponentColor) &&
  475.                         (origBoard->lastMove.toSquare.row == enPassantRow) &&
  476.                         (origBoard->lastMove.fromSquare.row == enPassantRow-2*advanceRowDir) &&
  477.                         (origBoard->lastMove.fromSquare.col == col + gDeltaCol[dir]) &&
  478.                         (origBoard->lastMove.toSquare.col == col + gDeltaCol[dir]) ) {
  479.                 CheckEPMove(origBoard,&moves,row,col,row,epCol,dir,&onSquare, &numMovesAdded);
  480. //            printf("** checking en passant (r,c)=(%d %d) ep=(%d %d)\n",
  481. //                row,col,origBoard->lastMove.fromSquare.row,origBoard->lastMove.fromSquare.col);
  482.             }
  483.         }
  484.     }
  485.  
  486.     return moves-origMoves;
  487. }
  488.  
  489. static UInt32 CreateLegalKnightMoves(Board *origBoard, SInt16 row, SInt16 col, ChessMove *moves)
  490. {
  491.     PieceColor ourColor = origBoard->sq[row][col].color;
  492.     PieceColor opponentColor = OtherColor(ourColor);
  493.     UInt32 numMovesAdded = 0;
  494.     Piece onSquare;
  495.     int dir,dist=0;
  496.     
  497.     for (dir=0; dir<8; dir++) {
  498.             if (!LegalKnightRelSquare(origBoard, row, col, dir, &onSquare)) continue;
  499.             if (onSquare.color == ourColor) continue;
  500.             if ((onSquare.color == opponentColor) || (onSquare.color == kEmpty) ){
  501.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  502.                 continue;
  503.             }
  504.     }
  505.     
  506.     return numMovesAdded;
  507. }
  508.  
  509. static UInt32 CreateLegalBishopMoves(Board *origBoard, SInt16 row, SInt16 col, ChessMove *moves)
  510. {
  511.     PieceColor ourColor = origBoard->sq[row][col].color;
  512.     PieceColor opponentColor = OtherColor(ourColor);
  513.     UInt32 numMovesAdded = 0;
  514.     Piece onSquare;
  515.     int dir,dist;
  516.     
  517.     for (dir=1; dir<8; dir+=2) {
  518.         for (dist=1; dist<8; dist++) {    /* check distance */
  519.             if (!LegalRelSquare(origBoard, row, col, dir, dist, &onSquare)) break;
  520.             if (onSquare.color == ourColor) break;
  521.             if (onSquare.color == opponentColor) {
  522.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  523.                 break;
  524.             } else if (onSquare.color == kEmpty) {
  525.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  526.                 continue;
  527.             }
  528.         }
  529.     }
  530.     
  531.     return numMovesAdded;
  532. }
  533.  
  534. static UInt32 CreateLegalRookMoves(Board *origBoard, SInt16 row, SInt16 col, ChessMove *moves)
  535. {
  536.     PieceColor ourColor = origBoard->sq[row][col].color;
  537.     PieceColor opponentColor = OtherColor(ourColor);
  538.     UInt32 numMovesAdded = 0;
  539.     Piece onSquare;
  540.     int dir,dist;
  541.     
  542.     for (dir=0; dir<8; dir+=2) {
  543.         for (dist=1; dist<8; dist++) {    /* check distance */
  544.             if (!LegalRelSquare(origBoard, row, col, dir, dist, &onSquare)) break;
  545.             if (onSquare.color == ourColor) break;
  546.             if (onSquare.color == opponentColor) {
  547.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  548.                 break;
  549.             } else if (onSquare.color == kEmpty) {
  550.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  551.                 continue;
  552.             }
  553.         }
  554.     }
  555.     
  556.     return numMovesAdded;
  557. }
  558.  
  559. static UInt32 CreateLegalQueenMoves(Board *origBoard, SInt16 row, SInt16 col, ChessMove *moves)
  560. {
  561.     PieceColor ourColor = origBoard->sq[row][col].color;
  562.     PieceColor opponentColor = OtherColor(ourColor);
  563.     UInt32 numMovesAdded = 0;
  564.     Piece onSquare;
  565.     int dir,dist;
  566.     
  567.     for (dir=0; dir<8; dir++) {
  568.         for (dist=1; dist<8; dist++) {    /* check distance */
  569.             if (!LegalRelSquare(origBoard, row, col, dir, dist, &onSquare)) break;
  570.             if (onSquare.color == ourColor) break;
  571.             if (onSquare.color == opponentColor) {
  572.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  573.                 break;
  574.             } else if (onSquare.color == kEmpty) {
  575.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  576.                 continue;
  577.             }
  578.         }
  579.     }
  580.     
  581.     return numMovesAdded;
  582. }
  583.  
  584. static UInt32 CreateLegalKingMoves(Board *origBoard, SInt16 row, SInt16 col, ChessMove *moves)
  585. {
  586.     PieceColor ourColor = origBoard->sq[row][col].color;
  587.     PieceColor opponentColor = OtherColor(ourColor);
  588.     UInt32 numMovesAdded = 0;
  589.     Piece onSquare;
  590.     int dir,dist,homeRow;
  591.  
  592.     if (ourColor==kWhite) {
  593.         homeRow = 0;
  594.     } else {
  595.         homeRow = 7;
  596.     }
  597.     
  598.     for (dir=0; dir<8; dir++) {
  599.         dist = 1;
  600.             if (!LegalRelSquare(origBoard, row, col, dir, dist, &onSquare)) continue;
  601.             if (onSquare.color == ourColor) continue;
  602.             if ( (onSquare.color == opponentColor) || (onSquare.color == kEmpty) ) {
  603.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  604.                 continue;
  605.             }
  606.     }
  607.     if ( (row==homeRow) && (col==kKingCol) && 
  608.                 origBoard->pieceNeverMoved[row][col] &&
  609.                 !SquareIsAttacked(origBoard, row, col)) {
  610.         ChessMove theMove;
  611.         if ( origBoard->pieceNeverMoved[row][0] &&
  612.             !SquareIsAttacked(origBoard, row, 0) && !SquareIsAttacked(origBoard, row, 1) && 
  613.             !SquareIsAttacked(origBoard, row, 2) && !SquareIsAttacked(origBoard, row, 3) && 
  614.             origBoard->sq[row][1].color==kEmpty && origBoard->sq[row][2].color==kEmpty &&
  615.             origBoard->sq[row][3].color==kEmpty ) {
  616.                 theMove.fromSquare.row = row;    theMove.fromSquare.col = col;
  617.                 theMove.toSquare.row = row;    theMove.toSquare.col = 1;
  618.                 theMove.capture = false;
  619.                 *moves = theMove;
  620.                 (moves)++;
  621.                 ++numMovesAdded;
  622.         }
  623.         if ( origBoard->pieceNeverMoved[row][7] &&
  624.             !SquareIsAttacked(origBoard, row, 7) && !SquareIsAttacked(origBoard, row, 6) && 
  625.             !SquareIsAttacked(origBoard, row, 5) && 
  626.             origBoard->sq[row][6].color==kEmpty && origBoard->sq[row][5].color==kEmpty ) {
  627.                 theMove.fromSquare.row = row;    theMove.fromSquare.col = col;
  628.                 theMove.toSquare.row = row;    theMove.toSquare.col = 6;
  629.                 theMove.capture = false;
  630.                 *moves = theMove;
  631.                 (moves)++;
  632.                 ++numMovesAdded;
  633.         }
  634.     }
  635.     
  636.     return numMovesAdded;
  637. }
  638.  
  639. static UInt32 CreateLegalMoves(Board *origBoard, SInt16 row, SInt16 col, ChessMove *moves)
  640. {
  641.     PieceRank rank = origBoard->sq[row][col].rank;
  642.     UInt32 numMovesAdded = 0;
  643.     switch (rank) {
  644.     case kPawn:
  645.         numMovesAdded = CreateLegalPawnMoves(origBoard,row,col,moves);
  646.         break;
  647.     case kKnight:
  648.         numMovesAdded = CreateLegalKnightMoves(origBoard,row,col,moves);
  649.         break;
  650.     case kBishop:
  651.         numMovesAdded = CreateLegalBishopMoves(origBoard,row,col,moves);
  652.         break;
  653.     case kRook:
  654.         numMovesAdded = CreateLegalRookMoves(origBoard,row,col,moves);
  655.         break;
  656.     case kQueen:
  657.         numMovesAdded = CreateLegalQueenMoves(origBoard,row,col,moves);
  658.         break;
  659.     case kKing:
  660.         numMovesAdded = CreateLegalKingMoves(origBoard,row,col,moves);
  661.         break;
  662.     default:
  663.         printf("** piece rank err %d\n",rank);
  664.         numMovesAdded = 0;
  665.         break;
  666.     }
  667.     return numMovesAdded;
  668. }
  669.  
  670. static UInt32 FindRemainingPieces(Board *b, ChessPiece piece[])
  671. {
  672.     int row,col;
  673.     UInt32 numPiecesRemaining = 0;
  674.     for (row=0; row<8; row++)
  675.         for (col=0; col<8; col++)
  676.             if (b->sq[row][col].color != kEmpty) {
  677.                 piece[numPiecesRemaining].whichColor = b->sq[row][col].color;
  678.                 piece[numPiecesRemaining].whichRank = b->sq[row][col].rank;
  679.                 piece[numPiecesRemaining].pieceLocation.row = row;
  680.                 piece[numPiecesRemaining].pieceLocation.col = col;
  681.                 numPiecesRemaining++;
  682.             }
  683.     return numPiecesRemaining;
  684. }
  685.  
  686. pascal void FindLegalChessMoves(
  687.     UInt32 numPriorMoves,
  688.     ChessMove priorMoves[],
  689.     UInt32 *numPiecesRemaining,
  690.     ChessPiece piecesRemaining[],
  691.     UInt32 *numLegalMoves,
  692.     ChessMove legalMoves[]
  693. ) {
  694.     int i;
  695.     SInt16 row,col;
  696.     Board bd;
  697.     UInt32 myNumLegalMoves = 0;
  698.     UInt32 myNumPiecesRemaining = 0;
  699.     PieceColor colorToMove = kWhite;
  700.     InitBoard(&bd);
  701.     PrintBoard(&bd);
  702.     for (i=0; i<numPriorMoves; i++) {
  703.         MovePiece(&bd,&priorMoves[i],colorToMove);
  704.         PrintBoard(&bd);
  705.         colorToMove = OtherColor(colorToMove);
  706.     }
  707.     myNumPiecesRemaining = FindRemainingPieces(&bd, piecesRemaining);
  708.     for (row=0; row<8; row++)
  709.         for (col=0; col<8; col++)
  710.             if (bd.sq[row][col].color == colorToMove)
  711.                 myNumLegalMoves += CreateLegalMoves(&bd,row,col,legalMoves+myNumLegalMoves);
  712.     *numPiecesRemaining= myNumPiecesRemaining;
  713.     *numLegalMoves = myNumLegalMoves;
  714. }
  715.